#include <iostream>
#include <stack>
using namespace std;

struct Block
{
    int row;
    int col;
    Block(int x, int y)
    {
        this->row = x;
        this->col = y;
    }

    bool operator!=(const Block &rhs)
    {
        if (this->row != rhs.row || this->col != rhs.col)
            return true;
        return false;
    }
};

Block getNoneVisitedBlockAndPreventCompress(bool **mark, Block point, int m, int n)
{
    Block resP(-1, -1);
    if (point.row - 1 >= 0 && mark[point.row - 1][point.col] == false)
    { //上节点满足条件
        resP.row = point.row - 1;
        resP.col = point.col;
        return resP;
    }
    if (point.col + 1 < n && mark[point.row][point.col + 1] == false)
    { //右节点满足条件
        resP.row = point.row;
        resP.col = point.col + 1;
        return resP;
    }
    if (point.row + 1 < m && mark[point.row + 1][point.col] == false)
    { //下节点满足条件
        resP.row = point.row + 1;
        resP.col = point.col;
        return resP;
    }
    if (point.col - 1 >= 0 && mark[point.row][point.col - 1] == false)
    { //左节点满足条件
        resP.row = point.row;
        resP.col = point.col - 1;
        return resP;
    }
    return resP;
}
void findOneMazePath(void *maze, int m, int n, const Block &startP, Block endP, stack<Block> &pointStack)
{
    //将给定的任意列数的二维数组还原为指针数组，以支持下标操作
    int **mazemap = new int *[m];
    for (int i = 0; i < m; ++i)
    {
        mazemap[i] = (int *)maze + i * n;
    }

    //起点和终点必须为无障碍结点，否则输入错误
    if (mazemap[startP.row][startP.col] == 1 || mazemap[endP.row][endP.col] == 1)
    {
        return;
    }

    //建立各个节点访问标记
    bool **mark = new bool *[m];
    for (int i = 0; i < m; ++i)
    {
        mark[i] = new bool[n];
    }
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            mark[i][j] = *((int *)maze + i * n + j);
        }
    }

    //将起点入栈
    pointStack.push(startP);
    mark[startP.row][startP.col] = true;

    //栈不空并且栈顶元素不为结束节点
    while (pointStack.empty() == false && pointStack.top() != endP)
    {
        Block findNoneVisitedBlock = getNoneVisitedBlockAndPreventCompress(mark, pointStack.top(), m, n);
        if (findNoneVisitedBlock.row == -1)
        {                     //没有未被访问的相邻节点
            pointStack.pop(); //回溯到上一个节点
            continue;
        }

        //入栈并设置访问标志为true
        mark[findNoneVisitedBlock.row][findNoneVisitedBlock.col] = true;
        pointStack.push(findNoneVisitedBlock);
    }
}

int main()
{
    int maze[10][12] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1},
        {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1},
        {1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1},
        {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1},
        {1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0},
        {1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};

    Block startP(1, 1);
    Block endP(7, 11);
    stack<Block> pointStack;
    findOneMazePath(maze, 10, 12, startP, endP, pointStack);

    //没有找到可行解
    if (pointStack.empty() == true)
    {
        cout << "no right path" << endl;
    }
    else
    {
        stack<Block> tempStack;
        cout << "路径（以x，y形式表示）：\n";
        while (pointStack.empty() == false)
        {
            tempStack.push(pointStack.top());
            pointStack.pop();
        }
        while (tempStack.empty() == false)
        {
            printf("(%d,%d) ", tempStack.top().row, tempStack.top().col);
            tempStack.pop();
        }
    }
    getchar();
    getchar();
}